using System;
using System.Collections.Generic;
using System.Text;

//TODO
namespace Mono.Boost.PriorityQueue
{
    class TwoTierHeap<T> : IRangeIndexedPriorityQueue<T> 
    {
                T[] Val;
        bool[] mark;
        int[] up;
        int[] left;
        int[] right;
        int[] down;
        int[] deg;
        int[] A;        
        bool[] exist;// do something about it !!!
        int Min;
        int size;
        IComparer<T> Cmp;
        public TwoTierHeap() { }
        public TwoTierHeap(int SizeOfHeap)
        {
            ((IRangeIndexedPriorityQueue<int>)this).Create(SizeOfHeap);
        }

        int IRangeIndexedPriorityQueue<T>.Size
        {
            get { return size; }
        }
        void IRangeIndexedPriorityQueue<T>.Create(int SizeOfHeap , IComparer<T> cmp)
        {
            Cmp = cmp;
            Val = new T[SizeOfHeap];
            mark = new bool[SizeOfHeap];
            up = new int[SizeOfHeap];
            down = new int[SizeOfHeap];
            left = new int[SizeOfHeap];
            right = new int[SizeOfHeap];
            deg = new int[SizeOfHeap];
            A = new int[(int)Math.Log(SizeOfHeap, 2) + 2];
            size = 0;
            Min = -1;

            exist = new bool[SizeOfHeap];
        }
        void IRangeIndexedPriorityQueue<T>.Create(int SizeOfHeap) {
            ((IRangeIndexedPriorityQueue<T>)this).Create(SizeOfHeap, Comparer<T>.Default);
        }
        void IRangeIndexedPriorityQueue<T>.Insert(int Key, T Value)
        {
            if (Min > -1)
            {
//                linkRoot( Key);
                if (Cmp.Compare(Val[Min],Value) > 0) Min = Key;
            }
            else {
                Min = Key;
                left[Key] = right[Key] = Key;
            }
            Val[Key] = Value;
            deg[Key] = 0;
            up[Key] = -1;
            down[Key] = -1;
            mark[Key] = false;
            exist[Key] = true;
            size++;
//            this.Validate();
        }
        void IRangeIndexedPriorityQueue<T>.DecreaseKey(int Key, T NewValue)
        {
 

        }
        int IRangeIndexedPriorityQueue<T>.TopKey
        {
            get
            {
                return Min;
            }
        }
        T IRangeIndexedPriorityQueue<T>.TopVal
        {
            get
            {
                return Val[Min];
            }
        }
        void IRangeIndexedPriorityQueue<T>.Pop()
        {
  //          if(size==1)Console.Write((this).ToString(null,null));
            int z = Min;
            int tmp = down[Min];
            if (tmp > -1)
            {
            }
            right[left[Min]] = right[Min];
            left[right[Min]] = left[Min];
            deg[Min] = -1;
            exist[Min] = false;
            if (size == 1) Min = -1;
            else {
                Min = left[Min];

            }
            size--;
//            this.Validate();

        }
        T IRangeIndexedPriorityQueue<T>.GetVal(int indx)
        {
                if (exist[indx]) return Val[indx];
                throw new IndexOutOfRangeException("there is no index :" + indx + " on heap");
        }

        void IRangeIndexedPriorityQueue<T>.SetVal(int indx, T value)
        {
                if (exist[indx]) ((IRangeIndexedPriorityQueue < T > )this).DecreaseKey(indx, value);
                else ((IRangeIndexedPriorityQueue<T>)this).Insert(indx, value);
        }
    }
}
